Mutually Uncorrelated Primers for DNA-Based Data Storage

摘要

We introduce the notion of weakly mutually uncorrelated (WMU) sequences,motivated by applications in DNA-based data storage systems and forsynchronization of communication devices. WMU sequences are characterized bythe property that no sufficiently long suffix of one sequence is the prefix ofthe same or another sequence. WMU sequences used for primer design in DNA-baseddata storage systems are also required to be at large mutual Hamming distancefrom each other, have balanced compositions of symbols, and avoid primer-dimerbyproducts. We derive bounds on the size of WMU and various constrained WMUcodes and present a number of constructions for balanced, error-correcting,primer-dimer free WMU codes using Dyck paths, prefix-synchronized and cycliccodes.